{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Zero Request Servers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #sorting #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #排序 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countServers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计没有收到请求的服务器数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数&nbsp;<code>n</code>&nbsp;，表示服务器的总数目，再给你一个下标从 <strong>0</strong>&nbsp;开始的 <strong>二维</strong>&nbsp;整数数组&nbsp;<code>logs</code>&nbsp;，其中&nbsp;<code>logs[i] = [server_id, time]</code>&nbsp;表示 id 为&nbsp;<code>server_id</code>&nbsp;的服务器在&nbsp;<code>time</code>&nbsp;时收到了一个请求。</p>\n",
    "\n",
    "<p>同时给你一个整数&nbsp;<code>x</code>&nbsp;和一个下标从 <strong>0</strong>&nbsp;开始的整数数组&nbsp;<code>queries</code>&nbsp; 。</p>\n",
    "\n",
    "<p>请你返回一个长度等于&nbsp;<code>queries.length</code>&nbsp;的数组&nbsp;<code>arr</code>&nbsp;，其中&nbsp;<code>arr[i]</code>&nbsp;表示在时间区间&nbsp;<code>[queries[i] - x, queries[i]]</code>&nbsp;内没有收到请求的服务器数目。</p>\n",
    "\n",
    "<p>注意时间区间是个闭区间。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 3, logs = [[1,3],[2,6],[1,5]], x = 5, queries = [10,11]\n",
    "<b>输出：</b>[1,2]\n",
    "<b>解释：</b>\n",
    "对于 queries[0]：id 为 1 和 2 的服务器在区间 [5, 10] 内收到了请求，所以只有服务器 3 没有收到请求。\n",
    "对于 queries[1]：id 为 2 的服务器在区间 [6,11] 内收到了请求，所以 id 为 1 和 3 的服务器在这个时间段内没有收到请求。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 3, logs = [[2,4],[2,1],[1,2],[3,1]], x = 2, queries = [3,4]\n",
    "<b>输出：</b>[0,1]\n",
    "<b>解释：</b>\n",
    "对于 queries[0]：区间 [1, 3] 内所有服务器都收到了请求。\n",
    "对于 queries[1]：只有 id 为 3 的服务器在区间 [2,4] 内没有收到请求。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= logs.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= queries.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>logs[i].length == 2</code></li>\n",
    "\t<li><code>1 &lt;= logs[i][0] &lt;= n</code></li>\n",
    "\t<li><code>1 &lt;= logs[i][1] &lt;= 10<sup>6</sup></code></li>\n",
    "\t<li><code>1 &lt;= x &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>x &lt;&nbsp;queries[i]&nbsp;&lt;= 10<sup>6</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-zero-request-servers](https://leetcode.cn/problems/count-zero-request-servers/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-zero-request-servers](https://leetcode.cn/problems/count-zero-request-servers/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3\\n[[1,3],[2,6],[1,5]]\\n5\\n[10,11]', '3\\n[[2,4],[2,1],[1,2],[3,1]]\\n2\\n[3,4]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, n: int, logs: List[List[int]], x: int, queries: List[int]) -> List[int]:\n",
    "        logs.sort(key=lambda x:x[1])\n",
    "        m=len(queries)\n",
    "        ans=[0]*m\n",
    "        cnt=[0]*(n+1)\n",
    "        left=right=0\n",
    "        out_of_range=n\n",
    "        for qi,q in sorted(enumerate(queries),key=lambda x:x[1]):\n",
    "            while right<len(logs) and logs[right][1]<=q:\n",
    "                i=logs[right][0]\n",
    "                if cnt[i]==0:\n",
    "                    out_of_range-=1\n",
    "                cnt[i]+=1\n",
    "                right+=1\n",
    "            while left<len(logs) and logs[left][1]<q-x:\n",
    "                i=logs[left][0]\n",
    "                cnt[i]-=1\n",
    "                if cnt[i]==0:\n",
    "                    out_of_range+=1\n",
    "                left+=1\n",
    "            ans[qi]=out_of_range\n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, n: int, logs: List[List[int]], x: int, queries: List[int]) -> List[int]:\n",
    "       logs.sort(key=lambda k:k[1])\n",
    "       res = [0] * len(queries)\n",
    "       i = 0\n",
    "       j = 0\n",
    "       cur = 0\n",
    "       cnts = [0] * (n + 1)\n",
    "       for t, id in sorted(zip(queries, range(len(queries))), key=lambda k:k[0]):\n",
    "          while j < len(logs) and logs[j][1] <= t:\n",
    "             cnts[logs[j][0]] += 1\n",
    "             if cnts[logs[j][0]] == 1:\n",
    "                cur += 1\n",
    "             j += 1\n",
    "          while i < len(logs) and logs[i][1] < t - x:\n",
    "             cnts[logs[i][0]] -= 1\n",
    "             if cnts[logs[i][0]] == 0:\n",
    "                cur -= 1\n",
    "             i += 1\n",
    "          res[id] = n - cur\n",
    "       return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def countServers(self, n: int, logs: List[List[int]], x: int, queries: List[int]) -> List[int]:\n",
    "\n",
    "        logs.sort(key=lambda p: p[1])  # 按照 time 排序\n",
    "\n",
    "        ans = [0] * len(queries)\n",
    "\n",
    "        cnt = [0] * (n + 1)\n",
    "\n",
    "        out_of_range = n\n",
    "\n",
    "        left = right = 0\n",
    "\n",
    "        for qi, q in sorted(enumerate(queries), key=lambda p: p[1]):\n",
    "\n",
    "            while right < len(logs) and logs[right][1] <= q:  # 进入窗口\n",
    "\n",
    "                i = logs[right][0]\n",
    "\n",
    "                if cnt[i] == 0: out_of_range -= 1\n",
    "\n",
    "                cnt[i] += 1\n",
    "\n",
    "                right += 1\n",
    "\n",
    "            while left < len(logs) and logs[left][1] < q - x:  # 离开窗口\n",
    "\n",
    "                i = logs[left][0]\n",
    "\n",
    "                cnt[i] -= 1\n",
    "\n",
    "                if cnt[i] == 0: out_of_range += 1\n",
    "\n",
    "                left += 1\n",
    "\n",
    "            ans[qi] = out_of_range\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, n: int, logs: List[List[int]], x: int, queries: List[int]) -> List[int]:\n",
    "        logs.sort(key=lambda p: p[1])  # 按照 time 排序\n",
    "        ans = [0] * len(queries)\n",
    "        cnt = [0] * (n + 1)\n",
    "        out_of_range = n\n",
    "        left = right = 0\n",
    "        for qi, q in sorted(enumerate(queries), key=lambda p: p[1]):\n",
    "            while right < len(logs) and logs[right][1] <= q:  # 进入窗口\n",
    "                i = logs[right][0]\n",
    "                if cnt[i] == 0: out_of_range -= 1\n",
    "                cnt[i] += 1\n",
    "                right += 1\n",
    "            while left < len(logs) and logs[left][1] < q - x:  # 离开窗口\n",
    "                i = logs[left][0]\n",
    "                cnt[i] -= 1\n",
    "                if cnt[i] == 0: out_of_range += 1\n",
    "                left += 1\n",
    "            ans[qi] = out_of_range\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, n: int, logs: List[List[int]], x: int, queries: List[int]) -> List[int]:\n",
    "        logs.sort(key = lambda x : x[1])\n",
    "        out = n\n",
    "        ans = [0] * len(queries)\n",
    "        cnt = [0] * (n + 1)\n",
    "        left = right = 0\n",
    "        for qi, q in sorted(enumerate(queries), key = lambda x : x[1]):\n",
    "            while right < len(logs) and logs[right][1] <= q:\n",
    "                i = logs[right][0]\n",
    "                if cnt[i] == 0:out -= 1\n",
    "                cnt[i] += 1\n",
    "                right += 1\n",
    "            while left < len(logs) and logs[left][1] < q - x:\n",
    "                i = logs[left][0]\n",
    "                cnt[i] -= 1\n",
    "                if cnt[i] == 0: out += 1\n",
    "                left += 1\n",
    "            ans[qi] = out\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, n: int, logs: List[List[int]], x: int, queries: List[int]) -> List[int]:\n",
    "        logs.sort(key=lambda x:x[1])\n",
    "        ans = [0] * len(queries)\n",
    "        cnt = [0] * (n + 1)\n",
    "        out_of_range = n\n",
    "        l = r = 0\n",
    "        for qi, q in sorted(enumerate(queries), key=lambda x:x[1]):\n",
    "            while r < len(logs) and logs[r][1] <= q:\n",
    "                i = logs[r][0]\n",
    "                if cnt[i] == 0: out_of_range -= 1\n",
    "                cnt[i] += 1\n",
    "                r += 1\n",
    "            while l < len(logs) and logs[l][1] < q - x:\n",
    "                i = logs[l][0]\n",
    "                cnt[i] -= 1\n",
    "                if cnt[i] == 0: out_of_range += 1\n",
    "                l += 1\n",
    "            ans[qi] = out_of_range\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, n: int, logs: List[List[int]], x: int, queries: List[int]) -> List[int]:\n",
    "        logs.sort(key=lambda p: p[1])  # 按照 time 排序\n",
    "        ans = [0] * len(queries)\n",
    "        cnt = [0] * (n + 1)\n",
    "        out_of_range = n\n",
    "        left = right = 0\n",
    "        for qi, q in sorted(enumerate(queries), key=lambda p: p[1]):\n",
    "            while right < len(logs) and logs[right][1] <= q:  # 进入窗口\n",
    "                i = logs[right][0]\n",
    "                if cnt[i] == 0: out_of_range -= 1\n",
    "                cnt[i] += 1\n",
    "                right += 1\n",
    "            while left < len(logs) and logs[left][1] < q - x:  # 离开窗口\n",
    "                i = logs[left][0]\n",
    "                cnt[i] -= 1\n",
    "                if cnt[i] == 0: out_of_range += 1\n",
    "                left += 1\n",
    "            ans[qi] = out_of_range\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, n: int, logs: List[List[int]], x: int, queries: List[int]) -> List[int]:\n",
    "        logs.sort(key=lambda p:p[1])\n",
    "        ans=[0]*len(queries)\n",
    "        cnt=[0]*(n+1)\n",
    "        outofrange=n\n",
    "        left=right=0\n",
    "        for qi,q in sorted(enumerate(queries),key=lambda p:p[1]):\n",
    "            while right<len(logs) and logs[right][1]<=q:\n",
    "                i=logs[right][0]\n",
    "                if cnt[i]==0:\n",
    "                    outofrange-=1\n",
    "                cnt[i]+=1\n",
    "                right+=1\n",
    "            while left<len(logs) and logs[left][1]<q-x:\n",
    "                i=logs[left][0]\n",
    "                cnt[i]-=1\n",
    "                if cnt[i]==0:\n",
    "                    outofrange+=1\n",
    "                left+=1\n",
    "            ans[qi]=outofrange\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    " \n",
    "class Solution:\n",
    "    def countServers(self, n: int, logs: List[List[int]], x: int, queries: List[int]) -> List[int]:\n",
    "        logs.sort(key=lambda p: p[1])  # 按照 time 排序\n",
    "        ans = [0] * len(queries)\n",
    "        cnt = [0] * (n + 1)\n",
    "        out_of_range = n\n",
    "        left = right = 0\n",
    "        for qi, q in sorted(enumerate(queries), key=lambda p: p[1]):\n",
    "            while right < len(logs) and logs[right][1] <= q:  # 进入窗口\n",
    "                i = logs[right][0]\n",
    "                if cnt[i] == 0: out_of_range -= 1\n",
    "                cnt[i] += 1\n",
    "                right += 1\n",
    "            while left < len(logs) and logs[left][1] < q - x:  # 离开窗口\n",
    "                i = logs[left][0]\n",
    "                cnt[i] -= 1\n",
    "                if cnt[i] == 0: out_of_range += 1\n",
    "                left += 1\n",
    "            ans[qi] = out_of_range\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, n: int, logs: List[List[int]], x: int, queries: List[int]) -> List[int]:\n",
    "        logs.sort(key=lambda p: p[1])  # 按照 time 排序\n",
    "        ans = [0] * len(queries)\n",
    "        cnt = [0] * (n + 1)\n",
    "        out_of_range = n\n",
    "        left = right = 0\n",
    "        for qi, q in sorted(enumerate(queries), key=lambda p: p[1]):\n",
    "            while right < len(logs) and logs[right][1] <= q:  # 进入窗口\n",
    "                i = logs[right][0]\n",
    "                if cnt[i] == 0: out_of_range -= 1\n",
    "                cnt[i] += 1\n",
    "                right += 1\n",
    "            while left < len(logs) and logs[left][1] < q - x:  # 离开窗口\n",
    "                i = logs[left][0]\n",
    "                cnt[i] -= 1\n",
    "                if cnt[i] == 0: out_of_range += 1\n",
    "                left += 1\n",
    "            ans[qi] = out_of_range\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, n: int, logs: List[List[int]], x: int, queries: List[int]) -> List[int]:\n",
    "        logs.sort(key=lambda p: p[1])  # 按照 time 排序\n",
    "        ans = [0] * len(queries)\n",
    "        cnt = [0] * (n + 1)\n",
    "        out_of_range = n\n",
    "        left = right = 0\n",
    "        for qi, q in sorted(enumerate(queries), key=lambda p: p[1]):\n",
    "            while right < len(logs) and logs[right][1] <= q:  # 进入窗口\n",
    "                i = logs[right][0]\n",
    "                if cnt[i] == 0: out_of_range -= 1\n",
    "                cnt[i] += 1\n",
    "                right += 1\n",
    "            while left < len(logs) and logs[left][1] < q - x:  # 离开窗口\n",
    "                i = logs[left][0]\n",
    "                cnt[i] -= 1\n",
    "                if cnt[i] == 0: out_of_range += 1\n",
    "                left += 1\n",
    "            ans[qi] = out_of_range\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, n: int, logs: List[List[int]], x: int, queries: List[int]) -> List[int]:\n",
    "        logs.sort(key=lambda p: p[1])  # 按照 time 排序\n",
    "        ans = [0] * len(queries)\n",
    "        cnt = [0] * (n + 1)\n",
    "        out_of_range = n\n",
    "        left = right = 0\n",
    "        for qi, q in sorted(enumerate(queries), key=lambda p: p[1]):\n",
    "            while right < len(logs) and logs[right][1] <= q:  # 进入窗口\n",
    "                i = logs[right][0]\n",
    "                if cnt[i] == 0: out_of_range -= 1\n",
    "                cnt[i] += 1\n",
    "                right += 1\n",
    "            while left < len(logs) and logs[left][1] < q - x:  # 离开窗口\n",
    "                i = logs[left][0]\n",
    "                cnt[i] -= 1\n",
    "                if cnt[i] == 0: out_of_range += 1\n",
    "                left += 1\n",
    "            ans[qi] = out_of_range\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, n: int, logs: List[List[int]], x: int, queries: List[int]) -> List[int]:\n",
    "        logs.sort(key=lambda p: p[1])  # 按照 time 排序\n",
    "        ans = [0] * len(queries)\n",
    "        cnt = [0] * (n + 1)\n",
    "        out_of_range = n\n",
    "        left = right = 0\n",
    "        for qi, q in sorted(enumerate(queries), key=lambda p: p[1]):\n",
    "            while right < len(logs) and logs[right][1] <= q:  # 进入窗口\n",
    "                i = logs[right][0]\n",
    "                if cnt[i] == 0: out_of_range -= 1\n",
    "                cnt[i] += 1\n",
    "                right += 1\n",
    "            while left < len(logs) and logs[left][1] < q - x:  # 离开窗口\n",
    "                i = logs[left][0]\n",
    "                cnt[i] -= 1\n",
    "                if cnt[i] == 0: out_of_range += 1\n",
    "                left += 1\n",
    "            ans[qi] = out_of_range\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, n: int, logs: List[List[int]], x: int, queries: List[int]) -> List[int]:\n",
    "        logs.sort(key= lambda p: p[1])\n",
    "        ans = [0] * len(queries)\n",
    "        cnt = [0] * (n + 1)\n",
    "        outOfRange = n\n",
    "        left = right = 0\n",
    "        for qi, q in sorted(enumerate(queries), key = lambda p: p[1]):\n",
    "            while right < len(logs) and logs[right][1] <= q:\n",
    "                i = logs[right][0]\n",
    "                if cnt[i] == 0: outOfRange -= 1\n",
    "                cnt[i] += 1\n",
    "                right += 1\n",
    "            while left < len(logs) and logs[left][1] < q - x:\n",
    "                i = logs[left][0]\n",
    "                cnt[i] -= 1\n",
    "                if cnt[i] == 0: outOfRange += 1\n",
    "                left += 1\n",
    "            ans[qi] = outOfRange\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, n: int, logs: List[List[int]], x: int, queries: List[int]) -> List[int]:\n",
    "        logs.sort(key=lambda p:p[1])\n",
    "        ans=[0]*len(queries)\n",
    "        cnt=[0]*(n+1)\n",
    "        out_of_range=n\n",
    "        left=right=0\n",
    "        for qi,q in sorted(enumerate(queries),key=lambda p:p[1]):\n",
    "            while right<len(logs) and logs[right][1]<=q:\n",
    "                i=logs[right][0]\n",
    "                if cnt[i]==0:out_of_range-=1\n",
    "                cnt[i]+=1\n",
    "                right+=1\n",
    "            while left<len(logs) and logs[left][1]<q-x:\n",
    "                i=logs[left][0]\n",
    "                cnt[i]-=1\n",
    "                if cnt[i]==0:out_of_range+=1\n",
    "                left+=1\n",
    "            ans[qi]=out_of_range\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def countServers(self, n: int, logs: List[List[int]], x: int, queries: List[int]) -> List[int]:\n",
    "\n",
    "        logs.sort(key=lambda p: p[1])  # 按照 time 排序\n",
    "\n",
    "        ans = [0] * len(queries)\n",
    "\n",
    "        cnt = [0] * (n + 1)\n",
    "\n",
    "        out_of_range = n\n",
    "\n",
    "        left = right = 0\n",
    "\n",
    "        for qi, q in sorted(enumerate(queries), key=lambda p: p[1]):\n",
    "\n",
    "            while right < len(logs) and logs[right][1] <= q:  # 进入窗口\n",
    "\n",
    "                i = logs[right][0]\n",
    "\n",
    "                if cnt[i] == 0: out_of_range -= 1\n",
    "\n",
    "                cnt[i] += 1\n",
    "\n",
    "                right += 1\n",
    "\n",
    "            while left < len(logs) and logs[left][1] < q - x:  # 离开窗口\n",
    "\n",
    "                i = logs[left][0]\n",
    "\n",
    "                cnt[i] -= 1\n",
    "\n",
    "                if cnt[i] == 0: out_of_range += 1\n",
    "\n",
    "                left += 1\n",
    "\n",
    "            ans[qi] = out_of_range\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, n: int, logs: List[List[int]], x: int, queries: List[int]) -> List[int]:\n",
    "        logs.sort(key=lambda p: p[1])\n",
    "        ans = [0] * len(queries)\n",
    "        cnt = [0] * (n + 1)\n",
    "        out_of_range = n\n",
    "        left = right = 0\n",
    "        for qi, q in sorted(enumerate(queries), key=lambda p: p[1]):\n",
    "            while right < len(logs) and logs[right][1] <= q:\n",
    "                i = logs[right][0]\n",
    "                if cnt[i] == 0: out_of_range -= 1\n",
    "                cnt[i] += 1\n",
    "                right += 1\n",
    "            while left < len(logs) and logs[left][1] < q - x:\n",
    "                i = logs[left][0]\n",
    "                cnt[i] -= 1\n",
    "                if cnt[i] == 0: out_of_range += 1\n",
    "                left += 1\n",
    "            ans[qi] = out_of_range\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, n: int, logs: List[List[int]], x: int, queries: List[int]) -> List[int]:\n",
    "        res = [0] * len(queries)\n",
    "        logs.sort(key=lambda x: x[1])\n",
    "        q = [(t, i) for i, t in enumerate(queries)]\n",
    "        q.sort()\n",
    "        count = [0] * (n + 1)\n",
    "        m, left, right, zero = len(logs), 0, 0, n\n",
    "        for t, i in q:\n",
    "            while right < m and logs[right][1] <= t:\n",
    "                server_id = logs[right][0]\n",
    "                count[server_id] += 1\n",
    "                if count[server_id] == 1:\n",
    "                    zero -= 1\n",
    "                right += 1\n",
    "            t -= x\n",
    "            while left < m and logs[left][1] < t:\n",
    "                server_id = logs[left][0]\n",
    "                count[server_id] -= 1\n",
    "                if count[server_id] == 0:\n",
    "                    zero += 1\n",
    "                left += 1\n",
    "            res[i] = zero\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, n: int, logs: List[List[int]], x: int, queries: List[int]) -> List[int]:\n",
    "        logs.sort(key=lambda p: p[1])  # 按照 time 排序\n",
    "        ans = [0] * len(queries)\n",
    "        cnt = [0] * (n + 1)\n",
    "        out_of_range = n\n",
    "        left = right = 0\n",
    "        for qi, q in sorted(enumerate(queries), key=lambda p: p[1]):\n",
    "            while right < len(logs) and logs[right][1] <= q:  # 进入窗口\n",
    "                i = logs[right][0]\n",
    "                if cnt[i] == 0: out_of_range -= 1\n",
    "                cnt[i] += 1\n",
    "                right += 1\n",
    "            while left < len(logs) and logs[left][1] < q - x:  # 离开窗口\n",
    "                i = logs[left][0]\n",
    "                cnt[i] -= 1\n",
    "                if cnt[i] == 0: out_of_range += 1\n",
    "                left += 1\n",
    "            ans[qi] = out_of_range\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, n: int, logs: List[List[int]], x: int, queries: List[int]) -> List[int]:\n",
    "        logs.sort(key = lambda p:p[1])\n",
    "        left = right = 0\n",
    "        cnt = [0]*(n+1)\n",
    "        ans = [0]*len(queries)\n",
    "        out_of_range = n\n",
    "        for qi, q in sorted(enumerate(queries),key = lambda p:p[1]):\n",
    "            while right < len(logs) and logs[right][1] <= q:\n",
    "                i = logs[right][0]\n",
    "                if cnt[i] == 0:out_of_range -=1\n",
    "                cnt[i] += 1\n",
    "                right +=1\n",
    "            while left < len(logs) and logs[left][1] < q - x:\n",
    "                i = logs[left][0]\n",
    "                cnt[i] -= 1\n",
    "                if cnt[i] == 0:out_of_range +=1\n",
    "                left +=1   \n",
    "            ans[qi] = out_of_range  \n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, n: int, logs: List[List[int]], x: int, queries: List[int]) -> List[int]:\n",
    "        logs.sort(key = lambda p:p[1])\n",
    "        left = right = 0\n",
    "        cnt = [0]*(n+1)\n",
    "        ans = [0]*len(queries)\n",
    "        out_of_range = n\n",
    "        for qi, q in sorted(enumerate(queries),key = lambda p:p[1]):\n",
    "            while right < len(logs) and logs[right][1] <= q:\n",
    "                i = logs[right][0]\n",
    "                if cnt[i] == 0:\n",
    "                    out_of_range -=1\n",
    "                cnt[i] += 1\n",
    "                right +=1\n",
    "            while left < len(logs) and logs[left][1] < q - x:\n",
    "                i = logs[left][0]\n",
    "                cnt[i] -= 1\n",
    "                if cnt[i] == 0:\n",
    "                    out_of_range +=1\n",
    "                left +=1   \n",
    "            ans[qi] = out_of_range  \n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, n: int, logs: List[List[int]], x: int, queries: List[int]) -> List[int]:\n",
    "        cnt = [0] * (n + 1)\n",
    "        ans = [0] * len(queries)\n",
    "        logs.sort(key=lambda q: q[1])\n",
    "        print(logs)\n",
    "        curr = n\n",
    "        left = right = 0\n",
    "        for i, q in sorted(enumerate(queries), key=lambda p: p[1]):\n",
    "            while right < len(logs) and logs[right][1] <= q:\n",
    "                xi = logs[right][0]\n",
    "                cnt[xi] += 1\n",
    "                if cnt[xi] == 1:\n",
    "                    curr -= 1\n",
    "                right += 1\n",
    "            while left < len(logs) and logs[left][1] < q - x:\n",
    "                xi = logs[left][0]\n",
    "                cnt[xi] -= 1\n",
    "                if cnt[xi] == 0:\n",
    "                    curr += 1\n",
    "                left += 1\n",
    "            ans[i] = curr\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, n: int, logs: List[List[int]], x: int, queries: List[int]) -> List[int]:\n",
    "        logs.sort(key = lambda p:p[1])\n",
    "        left = right = 0\n",
    "        cnt = [0]*(n+1)\n",
    "        ans = [0]*len(queries)\n",
    "        out_of_range = n\n",
    "        for qi, q in sorted(enumerate(queries),key = lambda p:p[1]):\n",
    "            while right < len(logs) and logs[right][1] <= q:\n",
    "                i = logs[right][0]\n",
    "                if cnt[i] == 0:\n",
    "                    out_of_range -=1\n",
    "                cnt[i] += 1\n",
    "                right +=1\n",
    "            while left < len(logs) and logs[left][1] < q - x:\n",
    "                i = logs[left][0]\n",
    "                cnt[i] -= 1\n",
    "                if cnt[i] == 0:\n",
    "                    out_of_range +=1\n",
    "                left +=1   \n",
    "            ans[qi] = out_of_range  \n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, n: int, logs: List[List[int]], x: int, queries: List[int]) -> List[int]:\n",
    "        \n",
    "        m = len(queries)\n",
    "        ans = [0]*m\n",
    "        ind = list(range(m))\n",
    "        ind.sort(key=lambda it: queries[it])\n",
    "        logs.sort(key=lambda it: it[1])\n",
    "        i1 = i2 = 0\n",
    "        k = len(logs)\n",
    "        dct = dict()\n",
    "        for j in ind:\n",
    "            left = queries[j]-x\n",
    "            right = queries[j]\n",
    "            while i2 < k and logs[i2][1] <= right:\n",
    "                dct[logs[i2][0]] = dct.get(logs[i2][0], 0) + 1\n",
    "                i2 += 1\n",
    "            while i1 < k and logs[i1][1] < left:\n",
    "                dct[logs[i1][0]] -= 1\n",
    "                if not dct[logs[i1][0]]:\n",
    "                    del dct[logs[i1][0]]\n",
    "                i1 += 1\n",
    "            ans[j] = n - len(dct)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, n: int, logs: List[List[int]], x: int, queries: List[int]) -> List[int]:\n",
    "        qs = set(queries)\n",
    "        res = {}\n",
    "        \n",
    "        logs.sort(key=lambda x: -x[1])\n",
    "        queue = deque()\n",
    "        ctr = Counter()\n",
    "        \n",
    "        for i in sorted(qs):\n",
    "            while logs and logs[-1][-1] <= i:\n",
    "                queue.append(logs.pop())\n",
    "                ctr[queue[-1][0]] += 1\n",
    "            \n",
    "            while queue and queue[0][-1] < i - x:\n",
    "                s = queue.popleft()[0]\n",
    "                ctr[s] -= 1\n",
    "                if not ctr[s]:\n",
    "                    ctr.pop(s)\n",
    "                    \n",
    "            if i in qs:\n",
    "                res[i] = n - len(ctr)\n",
    "            \n",
    "            # print(i, queue, ctr, res)\n",
    "        return [res[q] for q in queries]\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Fenwick:\n",
    "\n",
    "#     def __init__(self, n):\n",
    "#         self.tree = [0] * (n + 1)\n",
    "#         self.n = n\n",
    "    \n",
    "#     def update(self, x, val):\n",
    "#         while x <= self.n:\n",
    "#             self.tree[x] += val\n",
    "#             x += x & -x\n",
    "\n",
    "#     def query(self, x):\n",
    "#         res = 0\n",
    "#         while x > 0:\n",
    "#             res += self.tree[x]\n",
    "#             x -= x & -x\n",
    "#         return res\n",
    "\n",
    "#     def query_range(self, l, r):\n",
    "#         return self.query(r) - self.query(l - 1)\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, n: int, logs: List[List[int]], x: int, queries: List[int]) -> List[int]:\n",
    "\n",
    "        m = len(queries)\n",
    "        ans = [0] * m\n",
    "        \n",
    "        logs.sort(key=lambda x: x[1])\n",
    "        j = 0\n",
    "        l = 0\n",
    "        out = n\n",
    "        cnt = defaultdict(int)\n",
    "        for i, q in sorted(zip(range(m), queries), key=lambda t: t[1]):\n",
    "            while j < len(logs) and logs[j][1] <= q:\n",
    "                if cnt[logs[j][0]] == 0:\n",
    "                    out -= 1\n",
    "                cnt[logs[j][0]] += 1\n",
    "                j += 1\n",
    "            while l < j and logs[l][1] < q - x:\n",
    "                cnt[logs[l][0]] -= 1\n",
    "                if cnt[logs[l][0]] == 0:\n",
    "                    out += 1\n",
    "                l += 1\n",
    "            \n",
    "            ans[i] = out\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, n: int, logs: List[List[int]], x: int, queries: List[int]) -> List[int]:\n",
    "        logs.sort(key=lambda x : x[1])\n",
    "        m = len(queries)\n",
    "        ans = [n] * m\n",
    "        log_map = dict()\n",
    "        l, r = 0, 0\n",
    "        for i,q in sorted(enumerate(queries), key=lambda p : p[1]):\n",
    "            while r < len(logs) and logs[r][1] <= queries[i]:\n",
    "                if logs[r][0] in log_map:\n",
    "                    log_map[logs[r][0]] += 1\n",
    "                else:\n",
    "                    log_map[logs[r][0]] = 1\n",
    "                r += 1\n",
    "            while l < len(logs) and logs[l][1] < queries[i] - x:\n",
    "                if log_map[logs[l][0]] == 1:\n",
    "                    log_map.pop(logs[l][0])\n",
    "                else:\n",
    "                    log_map[logs[l][0]] -= 1\n",
    "                l += 1\n",
    "            ans[i] -= len(log_map)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, n: int, logs: List[List[int]], x: int, queries: List[int]) -> List[int]:\n",
    "        logs.sort(key=lambda x:x[1])\n",
    "        left=0\n",
    "        right=0\n",
    "       # n=len(logs)\n",
    "        mx=n\n",
    "        cnt=Counter()\n",
    "        ans=[0]*len(queries)\n",
    "        for qi,q in sorted(enumerate(queries),key= lambda x:x[1]):\n",
    "            while right < len(logs) and logs[right][1]<=q:\n",
    "                i =logs[right][0]\n",
    "                if cnt[i]==0:\n",
    "                    mx=mx-1\n",
    "                cnt[i]+=1\n",
    "                right+=1\n",
    "            \n",
    "            while left<len(logs) and logs[left][1]<(q-x):\n",
    "                i =logs[left][0]\n",
    "                cnt[i]-=1\n",
    "                if cnt[i]==0:\n",
    "                    mx=mx+1\n",
    "                left+=1\n",
    "            ans[qi]=mx\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, n: int, logs: List[List[int]], k: int, queries: List[int]) -> List[int]:\n",
    "        q=len(queries)\n",
    "        res=[0]*q\n",
    "        logs.sort(key=lambda x:-x[1])\n",
    "        cnt=defaultdict(int)\n",
    "        que=deque()\n",
    "        queries=[[i,x] for i,x in enumerate(queries)]\n",
    "        queries.sort(key=lambda x:x[1])\n",
    "        for i,x in queries:\n",
    "            while logs and logs[-1][1]<=x:\n",
    "                idx,time=logs.pop()\n",
    "                cnt[idx]+=1\n",
    "                que.append([idx,time])\n",
    "            while que and que[0][1]<x-k:\n",
    "                idx,time=que.popleft()\n",
    "                cnt[idx]-=1\n",
    "                if cnt[idx]==0:\n",
    "                    del cnt[idx]\n",
    "            res[i]=n-len(cnt)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, n: int, logs: List[List[int]], x: int, queries: List[int]) -> List[int]:\n",
    "        qr = sorted([(idx, q) for idx, q in enumerate(queries)], key = lambda x: x[1])\n",
    "        res = [0] * len(qr)\n",
    "        logs.sort(key = lambda x: x[1])\n",
    "        counter = collections.Counter()   \n",
    "        l = 0\n",
    "        r = 0\n",
    "        cnt = n \n",
    "        for idx, q in qr:\n",
    "            while l < len(logs) and logs[l][1] < q - x:\n",
    "                counter[logs[l][0]] -= 1 \n",
    "                if counter[logs[l][0]] == 0:\n",
    "                    cnt += 1 \n",
    "                l += 1 \n",
    "            while r < len(logs) and logs[r][1] <= q:\n",
    "                counter[logs[r][0]] += 1 \n",
    "                if counter[logs[r][0]] == 1:\n",
    "                    cnt -= 1 \n",
    "                r += 1\n",
    "            res[idx] = cnt    \n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Fenwick:\n",
    "\n",
    "    def __init__(self, n):\n",
    "        self.tree = [0] * (n + 1)\n",
    "        self.n = n\n",
    "    \n",
    "    def update(self, x, val):\n",
    "        while x <= self.n:\n",
    "            self.tree[x] += val\n",
    "            x += x & -x\n",
    "\n",
    "    def query(self, x):\n",
    "        res = 0\n",
    "        while x > 0:\n",
    "            res += self.tree[x]\n",
    "            x -= x & -x\n",
    "        return res\n",
    "\n",
    "    def query_range(self, l, r):\n",
    "        return self.query(r) - self.query(l - 1)\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, n: int, logs: List[List[int]], x: int, queries: List[int]) -> List[int]:\n",
    "\n",
    "        m = len(queries)\n",
    "        ans = [0] * m\n",
    "        bit = Fenwick(n)\n",
    "        logs.sort(key=lambda x: x[1])\n",
    "        j = 0\n",
    "        l = 0\n",
    "        # print(logs)\n",
    "        cnt = defaultdict(int)\n",
    "        for i, q in sorted(zip(range(m), queries), key=lambda t: t[1]):\n",
    "            while j < len(logs) and logs[j][1] <= q:\n",
    "                cnt[logs[j][0]] += 1\n",
    "                if cnt[logs[j][0]] == 1:\n",
    "                    bit.update(logs[j][0], 1)\n",
    "                j += 1\n",
    "            while l < j and logs[l][1] < q - x:\n",
    "                cnt[logs[l][0]] -= 1\n",
    "                if cnt[logs[l][0]] == 0:\n",
    "                    bit.update(logs[l][0], -1)\n",
    "                l += 1\n",
    "            # print(bit.tree, bit.query_range(1, n), j)\n",
    "            ans[i] = n - bit.query_range(1, n)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Fenwick:\n",
    "\n",
    "    def __init__(self, n):\n",
    "        self.tree = [0] * (n + 1)\n",
    "        self.n = n\n",
    "    \n",
    "    def update(self, x, val):\n",
    "        while x <= self.n:\n",
    "            self.tree[x] += val\n",
    "            x += x & -x\n",
    "\n",
    "    def query(self, x):\n",
    "        res = 0\n",
    "        while x > 0:\n",
    "            res += self.tree[x]\n",
    "            x -= x & -x\n",
    "        return res\n",
    "\n",
    "    def query_range(self, l, r):\n",
    "        return self.query(r) - self.query(l - 1)\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, n: int, logs: List[List[int]], x: int, queries: List[int]) -> List[int]:\n",
    "\n",
    "        m = len(queries)\n",
    "        ans = [0] * m\n",
    "        bit = Fenwick(n)\n",
    "        logs.sort(key=lambda x: x[1])\n",
    "        j = 0\n",
    "        l = 0\n",
    "        # print(logs)\n",
    "        cnt = defaultdict(int)\n",
    "        for i, q in sorted(zip(range(m), queries), key=lambda t: t[1]):\n",
    "            while j < len(logs) and logs[j][1] <= q:\n",
    "                cnt[logs[j][0]] += 1\n",
    "                if cnt[logs[j][0]] == 1:\n",
    "                    bit.update(logs[j][0], 1)\n",
    "                j += 1\n",
    "            while l < j and logs[l][1] < q - x:\n",
    "                cnt[logs[l][0]] -= 1\n",
    "                if cnt[logs[l][0]] == 0:\n",
    "                    bit.update(logs[l][0], -1)\n",
    "                l += 1\n",
    "            # print(bit.tree, bit.query_range(1, n), j)\n",
    "            ans[i] = n - bit.query_range(1, n)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, n: int, logs: List[List[int]], x: int, queries: List[int]) -> List[int]:\n",
    "        qr = sorted([(idx, t) for idx, t in enumerate(queries)], key = lambda x: x[1])\n",
    "        logs.sort(key = lambda x: x[1])\n",
    "        counter = collections.Counter()\n",
    "        cnt = n \n",
    "        res = [0] * len(queries)\n",
    "        l, r = 0, 0\n",
    "        for idx, time in qr:\n",
    "            while l < len(logs) and logs[l][1] < time - x:\n",
    "                counter[logs[l][0]] -= 1 \n",
    "                if counter[logs[l][0]] == 0:\n",
    "                    cnt += 1 \n",
    "                l += 1 \n",
    "            while r < len(logs) and logs[r][1] <= time:\n",
    "                counter[logs[r][0]] += 1 \n",
    "                if counter[logs[r][0]] == 1:\n",
    "                    cnt -= 1 \n",
    "                r += 1 \n",
    "            res[idx] = cnt \n",
    "        return res \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, n: int, logs: List[List[int]], x: int, queries: List[int]) -> List[int]:\n",
    "        ans = [0] * len(queries)\n",
    "        queries = [(x, i) for i, x in enumerate(queries)]\n",
    "        queries.sort()\n",
    "        logs.sort(key=lambda x:(x[1], x[0]))\n",
    "        cnt = defaultdict(int)\n",
    "        ptr, m = 0, len(logs)\n",
    "        q = deque()\n",
    "        for t, idx in queries:\n",
    "            left, right = t - x, t\n",
    "            while ptr < m and logs[ptr][1] <= right:\n",
    "                q.append(logs[ptr])\n",
    "                cnt[logs[ptr][0]] += 1\n",
    "                ptr += 1\n",
    "            while q and q[0][1] < left:\n",
    "                i, tt = q.popleft()\n",
    "                cnt[i] -= 1\n",
    "                if cnt[i] == 0:del cnt[i]\n",
    "            ans[idx] = n - len(cnt)\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, n: int, logs: List[List[int]], x: int, queries: List[int]) -> List[int]:\n",
    "        order=copy.deepcopy(queries)\n",
    "        queries.sort()\n",
    "        ans=collections.defaultdict(int)\n",
    "        c=collections.Counter()\n",
    "        logs=sorted(logs,key=lambda x:x[1])\n",
    "        ll=len(logs)\n",
    "        i=0\n",
    "        heap=collections.deque()\n",
    "        for q in queries:\n",
    "            while i<ll and logs[i][1]<=q:\n",
    "                if logs[i][1]+x>=q:\n",
    "                    c[logs[i][0]]+=1\n",
    "                    heap.append((logs[i][1]+x,logs[i][0]))\n",
    "                i+=1\n",
    "            ret=0\n",
    "            while heap and heap[0][0]<q:\n",
    "                tp1,tp2=heap.popleft() \n",
    "                c[tp2]-=1\n",
    "                if c[tp2]==0:\n",
    "                    del c[tp2]\n",
    "            ret=len(c)\n",
    "            ans[q]=ret\n",
    "        anss=[]\n",
    "        for o in order:\n",
    "            anss.append(n-ans[o])\n",
    "        return anss"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, n: int, logs: List[List[int]], x: int, queries: List[int]) -> List[int]:\n",
    "        mapping = {}\n",
    "        logs.sort(key=lambda x:x[1])\n",
    "        queries = sorted([[q,i] for i,q in enumerate(queries)])\n",
    "        left, right = 0, 0\n",
    "        result = [0]*len(queries)\n",
    "        for q, i in queries:\n",
    "            while(right < len(logs) and logs[right][1] <= q):\n",
    "                server_id, time = logs[right]\n",
    "                if(server_id not in mapping):\n",
    "                    mapping[server_id] = 1\n",
    "                else:\n",
    "                    mapping[server_id] += 1\n",
    "                right += 1\n",
    "            while(left < len(logs) and logs[left][1] < q - x):\n",
    "                server_id, time = logs[left]\n",
    "                mapping[server_id] -= 1\n",
    "                if(mapping[server_id] == 0):\n",
    "                    del mapping[server_id]\n",
    "                left += 1\n",
    "            result[i] = n-len(mapping)\n",
    "        return result\n",
    "\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, n: int, logs: List[List[int]], x: int, queries: List[int]) -> List[int]:\n",
    "        mapping = {}\n",
    "        logs.sort(key=lambda x:x[1])\n",
    "        queries = sorted([[q,i] for i,q in enumerate(queries)])\n",
    "        left, right = 0, 0\n",
    "        result = [0]*len(queries)\n",
    "        for q, i in queries:\n",
    "            while(right < len(logs) and logs[right][1] <= q):\n",
    "                server_id, time = logs[right]\n",
    "                if(server_id not in mapping):\n",
    "                    mapping[server_id] = 1\n",
    "                else:\n",
    "                    mapping[server_id] += 1\n",
    "                right += 1\n",
    "            while(left < len(logs) and logs[left][1] < q - x):\n",
    "                server_id, time = logs[left]\n",
    "                mapping[server_id] -= 1\n",
    "                if(mapping[server_id] == 0):\n",
    "                    del mapping[server_id]\n",
    "                left += 1\n",
    "            result[i] = n-len(mapping)\n",
    "        return result\n",
    "\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, n: int, logs: List[List[int]], x: int, queries: List[int]) -> List[int]:\n",
    "        mapping = {}\n",
    "        logs.sort(key=lambda x:x[1])\n",
    "        queries = sorted([[q,i] for i,q in enumerate(queries)])\n",
    "        left, right = 0, 0\n",
    "        result = [0]*len(queries)\n",
    "        for q, i in queries:\n",
    "            while(right < len(logs) and logs[right][1] <= q):\n",
    "                server_id, time = logs[right]\n",
    "                if(server_id not in mapping):\n",
    "                    mapping[server_id] = 1\n",
    "                else:\n",
    "                    mapping[server_id] += 1\n",
    "                right += 1\n",
    "            while(left < len(logs) and logs[left][1] < q - x):\n",
    "                server_id, time = logs[left]\n",
    "                mapping[server_id] -= 1\n",
    "                if(mapping[server_id] == 0):\n",
    "                    del mapping[server_id]\n",
    "                left += 1\n",
    "            result[i] = n - len(mapping)\n",
    "        return result\n",
    "\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, n1: int, logs: List[List[int]], x: int, queries: List[int]) -> List[int]:\n",
    "        queries = [(q, i) for i, q in enumerate(queries)]\n",
    "        queries.sort()\n",
    "        \n",
    "        logs.sort(key=lambda x: x[1])\n",
    "        k = 0\n",
    "        j = 0\n",
    "        n = len(logs)\n",
    "        d = dict()\n",
    "        res = [0] * len(queries)\n",
    "        \n",
    "        print(queries)\n",
    "        print(logs)\n",
    "        for q, i in queries:\n",
    "            while k < n and logs[k][1] <= q:\n",
    "                if logs[k][0] not in d:\n",
    "                    d[logs[k][0]] = 1\n",
    "                else:\n",
    "                    d[logs[k][0]] += 1\n",
    "                k += 1\n",
    "            while j < n and q - x > logs[j][1]:\n",
    "                d[logs[j][0]] -= 1\n",
    "                if d[logs[j][0]] == 0:\n",
    "                    del d[logs[j][0]]\n",
    "                j += 1\n",
    "            res[i] = n1 - len(d)\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, n: int, logs: List[List[int]], x: int, queries: List[int]) -> List[int]:\n",
    "        order=copy.deepcopy(queries)\n",
    "        queries.sort()\n",
    "        ans=collections.defaultdict(int)\n",
    "        c=collections.Counter()\n",
    "        logs=sorted(logs,key=lambda x:x[1])\n",
    "        ll=len(logs)\n",
    "        i=0\n",
    "        heap=collections.deque()\n",
    "        for q in queries:\n",
    "            while i<ll and logs[i][1]<=q:\n",
    "                if logs[i][1]+x>=q:\n",
    "                    c[logs[i][0]]+=1\n",
    "                    heap.append((logs[i][1]+x,logs[i][0]))\n",
    "                i+=1\n",
    "            #ret=0\n",
    "            while heap and heap[0][0]<q:\n",
    "                tp1,tp2=heap.popleft() \n",
    "                c[tp2]-=1\n",
    "                if c[tp2]==0:\n",
    "                    del c[tp2]\n",
    "            ret=len(c)\n",
    "            ans[q]=ret\n",
    "        anss=[]\n",
    "        for o in order:\n",
    "            anss.append(n-ans[o])\n",
    "        return anss"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, n: int, logs: List[List[int]], x: int, queries: List[int]) -> List[int]:\n",
    "        \n",
    "        t = {}\n",
    "        r = 0\n",
    "        l = 0\n",
    "        logs.sort(key=lambda x:x[1]) # 注意必须加关键字，否则logs的时间顺序还是乱的\n",
    "        qs = sorted([queries[j],j] for j in range(len(queries))) #打包排序填答案就方便了\n",
    "        res = [0]*len(qs)\n",
    "\n",
    "        for q,idx in qs:\n",
    "            while r<len(logs) and logs[r][1]<=q: #先移动右指针，并给哈希表添加元素\n",
    "                t[logs[r][0]]=t.get(logs[r][0],0)+1\n",
    "                r+=1\n",
    "            while l<len(logs) and logs[l][1]<q-x: #再移动左指针，并给哈希表删除元素\n",
    "                t[logs[l][0]]-=1\n",
    "                if not t[logs[l][0]]: del t[logs[l][0]]\n",
    "                l+=1\n",
    "            res[idx]=n-len(t) # 直接填当前q的答案\n",
    "        return res\n",
    "\n",
    "\n",
    "            \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, n: int, logs: List[List[int]], x: int, queries: List[int]) -> List[int]:\n",
    "        order=copy.deepcopy(queries)\n",
    "        queries.sort()\n",
    "        ans=collections.defaultdict(int)\n",
    "        c=collections.Counter()\n",
    "        #for i in range(n+1):\n",
    "        #    c[n]=9999999\n",
    "        #logs.append([0,999999999])\n",
    "        logs=sorted(logs,key=lambda x:x[1])\n",
    "        lq,ll=len(queries),len(logs)\n",
    "        i=0\n",
    "        heap=[]\n",
    "        for q in queries:\n",
    "            #print(q,logs[i][1])\n",
    "            while i<ll and logs[i][1]<=q:\n",
    "                if logs[i][1]+x>=q:\n",
    "                    c[logs[i][0]]+=1\n",
    "                    heapq.heappush(heap,(logs[i][1]+x,logs[i][0]))\n",
    "                i+=1\n",
    "                #rint(i)\n",
    "            ret=0\n",
    "            while heap and heap[0][0]<q:\n",
    "                tp1,tp2=heapq.heappop(heap) \n",
    "                c[tp2]-=1\n",
    "                if c[tp2]==0:\n",
    "                    del c[tp2]\n",
    "            ret=len(c)\n",
    "            #print(q,c,ret)\n",
    "            ans[q]=ret\n",
    "        #print(ans)\n",
    "        anss=[]\n",
    "        for o in order:\n",
    "            #print(o)\n",
    "            anss.append(n-ans[o])\n",
    "        return anss"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, n: int, logs: List[List[int]], x: int, queries: List[int]) -> List[int]:\n",
    "        order=copy.deepcopy(queries)\n",
    "        queries.sort()\n",
    "        ans=collections.defaultdict(int)\n",
    "        c=collections.Counter()\n",
    "        logs=sorted(logs,key=lambda x:x[1])\n",
    "        lq,ll=len(queries),len(logs)\n",
    "        i=0\n",
    "        heap=[]\n",
    "        for q in queries:\n",
    "            while i<ll and logs[i][1]<=q:\n",
    "                if logs[i][1]+x>=q:\n",
    "                    c[logs[i][0]]+=1\n",
    "                    heapq.heappush(heap,(logs[i][1]+x,logs[i][0]))\n",
    "                i+=1\n",
    "            ret=0\n",
    "            while heap and heap[0][0]<q:\n",
    "                tp1,tp2=heapq.heappop(heap) \n",
    "                c[tp2]-=1\n",
    "                if c[tp2]==0:\n",
    "                    del c[tp2]\n",
    "            ret=len(c)\n",
    "            ans[q]=ret\n",
    "        anss=[]\n",
    "        for o in order:\n",
    "            anss.append(n-ans[o])\n",
    "        return anss"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, n: int, logs: List[List[int]], x: int, queries: List[int]) -> List[int]:\n",
    "        q_len = len(queries)\n",
    "        l_len = len(logs)\n",
    "        logs.sort(key = lambda x: x[1])\n",
    "        log_sorted_by_time_queue = deque()\n",
    "        right = 0\n",
    "        server_appear_cnt = Counter()\n",
    "        ans = [-1] * q_len\n",
    "        for i, time in sorted(zip(range(q_len), queries), key = lambda x : x[1]):\n",
    "            while right < l_len and logs[right][1] <= time:\n",
    "                server_id = logs[right][0]\n",
    "                log_sorted_by_time_queue.append([logs[right][1], server_id])\n",
    "                server_appear_cnt[server_id] += 1\n",
    "                right += 1\n",
    "            #print(\"before -\", server_appear_cnt)\n",
    "            while log_sorted_by_time_queue and log_sorted_by_time_queue[0][0] < time - x:\n",
    "                #print(\"popping -\", log_sorted_by_time_queue[0])\n",
    "                _, server_id = log_sorted_by_time_queue.popleft()\n",
    "                server_appear_cnt[server_id] -= 1\n",
    "                if server_appear_cnt[server_id] == 0:\n",
    "                    server_appear_cnt.pop(server_id)\n",
    "            #print(\"after -\", server_appear_cnt)\n",
    "            ans[i] = n - len(server_appear_cnt)\n",
    "        return ans\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, n: int, logs: List[List[int]], x: int, queries: List[int]) -> List[int]:\n",
    "\n",
    "        # sliding window + sort\n",
    "\n",
    "        ret = [0] * len(queries)\n",
    "\n",
    "        queries = [(q, i) for i, q in enumerate(queries)]\n",
    "        queries.sort()\n",
    "\n",
    "        logs = [(t, s) for s, t in logs]\n",
    "        logs.sort()\n",
    "\n",
    "        # print(logs)\n",
    "        # print(queries)\n",
    "\n",
    "        start = 0\n",
    "        end = 0\n",
    "        log_idx_r = 0\n",
    "        log_idx_l = 0\n",
    "        d = defaultdict(int)\n",
    "        for q, idx in queries:\n",
    "\n",
    "            while log_idx_r < len(logs):\n",
    "                if logs[log_idx_r][0] <= q:\n",
    "                    d[logs[log_idx_r][1]] += 1\n",
    "                    log_idx_r += 1\n",
    "                else:\n",
    "                    break\n",
    "            \n",
    "            while log_idx_l <= log_idx_r and log_idx_l < len(logs):\n",
    "\n",
    "                if logs[log_idx_l][0] < q - x:\n",
    "                    d[logs[log_idx_l][1]] -= 1\n",
    "                    if d[logs[log_idx_l][1]] == 0:\n",
    "                        del d[logs[log_idx_l][1]]\n",
    "                    log_idx_l += 1\n",
    "                else:\n",
    "                    break\n",
    "            \n",
    "            # print(f'q: {q}, idx: {idx}, d: {d}')\n",
    "            ret[idx] = n - len(d)\n",
    "        \n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, n: int, logs: List[List[int]], x: int, queries: List[int]) -> List[int]:\n",
    "        logs.sort(key=lambda x:x[1])\n",
    "        q2=[]\n",
    "        for idx,e in enumerate(queries):\n",
    "            q2.append((e,idx))\n",
    "        q2.sort(key=lambda x:x[0])\n",
    "        d=dict()\n",
    "        r=[]\n",
    "        pos1=0\n",
    "        pos2=0\n",
    "        for e in q2:\n",
    "            st=e[0]-x\n",
    "            et=e[0]\n",
    "            while(True):\n",
    "                if pos2==len(logs):break\n",
    "                if logs[pos2][1]<=et:\n",
    "                    if logs[pos2][0] in d:\n",
    "                        d[logs[pos2][0]]+=1\n",
    "                    else:\n",
    "                        d[logs[pos2][0]]=1\n",
    "                else:\n",
    "                    break\n",
    "                pos2+=1\n",
    "            while(True):\n",
    "                if pos1==len(logs):break\n",
    "                if logs[pos1][1]<st:\n",
    "                    if logs[pos1][0] in d:\n",
    "                        if d[logs[pos1][0]]>0:\n",
    "                            d[logs[pos1][0]]-=1\n",
    "                            if d[logs[pos1][0]]==0:\n",
    "                                del d[logs[pos1][0]]\n",
    "                        else:\n",
    "                            del d[logs[pos1][0]]\n",
    "                else:\n",
    "                    break\n",
    "                pos1+=1\n",
    "            r.append((n-len(d),e[1]))\n",
    "        r.sort(key=lambda x:x[1])\n",
    "        return [x[0] for x in r]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, n: int, logs: List[List[int]], x: int, queries: List[int]) -> List[int]:\n",
    "        logs.sort(key=lambda i: i[1])\n",
    "\n",
    "\n",
    "        j = 0\n",
    "        k = 0\n",
    "        dict1 = {}\n",
    "        result=[]\n",
    "        for i in range(len(queries)):\n",
    "            queries[i]=[i,queries[i]]\n",
    "        queries.sort(key=lambda i:i[1])\n",
    "        result=[0 for i in range(len(queries))]\n",
    "        for query in queries:\n",
    "            i=query[1]\n",
    "            while k < len(logs) and logs[k][1] <= i:\n",
    "                if logs[k][0] in dict1.keys():\n",
    "                    dict1[logs[k][0]] += 1\n",
    "                else:\n",
    "                    dict1[logs[k][0]] = 1\n",
    "                k = k + 1\n",
    "            while j <= len(logs) - 1 and logs[j][1] < i - x:\n",
    "                if dict1[logs[j][0]] <= 1:\n",
    "                    dict1.pop(logs[j][0])\n",
    "                else:\n",
    "                    dict1[logs[j][0]] -= 1\n",
    "                j += 1\n",
    "            result[query[0]]=(n- len(dict1.keys()))\n",
    "\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT(object):\n",
    "    def __init__(self,n : int):\n",
    "        self.a = [0] * (n + 10)\n",
    "        self.n = n\n",
    "\n",
    "    def lowbit(self,x : int) -> int:\n",
    "        return x & (-x)\n",
    "\n",
    "    def update(self,i : int,k : int):\n",
    "        while i <= self.n:\n",
    "            self.a[i] += k\n",
    "            i += self.lowbit(i)\n",
    "\n",
    "    def query(self,i : int) -> int:\n",
    "        res = 0\n",
    "        while i > 0:\n",
    "            res += self.a[i]\n",
    "            i -= self.lowbit(i)\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, k: int, logs: List[List[int]], x: int, queries: List[int]) -> List[int]:\n",
    "        que = []\n",
    "        m,n = len(queries),len(logs)\n",
    "\n",
    "        logs.sort(key= lambda x : x[1])\n",
    "        bit = BIT(n)\n",
    "\n",
    "        ans = [0] * m\n",
    "\n",
    "        def find(x : int) -> int:\n",
    "            l,r = 0,n - 1\n",
    "            while l < r:\n",
    "                mid = (l + r) >> 1\n",
    "                if logs[mid][1] >= x:\n",
    "                    r = mid\n",
    "                else:\n",
    "                    l = mid + 1\n",
    "            return l\n",
    "\n",
    "        def find2(x : int) -> int:\n",
    "            l,r = 0,n - 1\n",
    "\n",
    "            while l < r:\n",
    "                mid = (l + r + 1) >> 1\n",
    "                if logs[mid][1] <= x:\n",
    "                    l = mid\n",
    "                else:\n",
    "                    r = mid - 1\n",
    "            return l \n",
    "        # print(logs)\n",
    "        que = []\n",
    "        for i in range(m):\n",
    "            t_l,t_r = queries[i] - x,queries[i]\n",
    "            l = find(t_l)\n",
    "            if l == n - 1 and logs[l][1] < queries[i] - x:\n",
    "                que.append((n + 10,n + 10,i))\n",
    "                continue\n",
    "\n",
    "            r = find2(t_r)\n",
    "            if r == 0 and logs[r][1] > queries[i]:\n",
    "                que.append((-1,-1,i))\n",
    "                continue\n",
    "            que.append((l + 1,r + 1,i))\n",
    "\n",
    "        que.sort(key = lambda x:x[1])\n",
    "\n",
    "        vis = {}\n",
    "        p = 1\n",
    "        for i in range(m):\n",
    "            l,r,idx = que[i]\n",
    "            if l > n or r <= 0:\n",
    "                ans[idx] = k\n",
    "                continue\n",
    "\n",
    "            for j in range(p,r + 1):\n",
    "                if logs[j - 1][0] in vis:\n",
    "                    bit.update(vis[logs[j - 1][0]], -1)\n",
    "                \n",
    "                bit.update(j,1)\n",
    "                vis[logs[j - 1][0]] = j\n",
    "\n",
    "            p = r + 1\n",
    "            ans[idx] = k - (bit.query(r) - bit.query(l - 1))\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT(object):\n",
    "    def __init__(self,n : int):\n",
    "        self.a = [0] * (n + 10)\n",
    "        self.n = n\n",
    "\n",
    "    def lowbit(self,x : int) -> int:\n",
    "        return x & (-x)\n",
    "\n",
    "    def update(self,i : int,k : int):\n",
    "        while i <= self.n:\n",
    "            self.a[i] += k\n",
    "            i += self.lowbit(i)\n",
    "\n",
    "    def query(self,i : int) -> int:\n",
    "        res = 0\n",
    "        while i > 0:\n",
    "            res += self.a[i]\n",
    "            i -= self.lowbit(i)\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, k: int, logs: List[List[int]], x: int, queries: List[int]) -> List[int]:\n",
    "        que = []\n",
    "        m,n = len(queries),len(logs)\n",
    "\n",
    "        logs.sort(key= lambda x : x[1])\n",
    "        bit = BIT(n)\n",
    "\n",
    "        ans = [0] * m\n",
    "\n",
    "        def find(x : int) -> int:\n",
    "            l,r = 0,n - 1\n",
    "            while l < r:\n",
    "                mid = (l + r) >> 1\n",
    "                if logs[mid][1] >= x:\n",
    "                    r = mid\n",
    "                else:\n",
    "                    l = mid + 1\n",
    "            return l\n",
    "\n",
    "        def find2(x : int) -> int:\n",
    "            l,r = 0,n - 1\n",
    "\n",
    "            while l < r:\n",
    "                mid = (l + r + 1) >> 1\n",
    "                if logs[mid][1] <= x:\n",
    "                    l = mid\n",
    "                else:\n",
    "                    r = mid - 1\n",
    "            return l \n",
    "        # print(logs)\n",
    "        que = []\n",
    "        for i in range(m):\n",
    "            t_l,t_r = queries[i] - x,queries[i]\n",
    "            l = find(t_l)\n",
    "            if l == n - 1 and logs[l][1] < queries[i] - x:\n",
    "                que.append((n + 10,n + 10,i))\n",
    "                continue\n",
    "\n",
    "            r = find2(t_r)\n",
    "            if r == 0 and logs[r][1] > queries[i]:\n",
    "                que.append((-1,-1,i))\n",
    "                continue\n",
    "            que.append((l + 1,r + 1,i))\n",
    "\n",
    "        que.sort(key = lambda x:x[1])\n",
    "\n",
    "        vis = {}\n",
    "        p = 1\n",
    "        for i in range(m):\n",
    "            l,r,idx = que[i]\n",
    "            if l > n or r <= 0:\n",
    "                ans[idx] = k\n",
    "                continue\n",
    "\n",
    "            for j in range(p,r + 1):\n",
    "                if logs[j - 1][0] in vis:\n",
    "                    bit.update(vis[logs[j - 1][0]], -1)\n",
    "                \n",
    "                bit.update(j,1)\n",
    "                vis[logs[j - 1][0]] = j\n",
    "\n",
    "            p = r + 1\n",
    "            ans[idx] = k - (bit.query(r) - bit.query(l - 1))\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, n: int, logs: List[List[int]], x: int, queries: List[int]) -> List[int]:\n",
    "        time = defaultdict(list)\n",
    "        for idx, t in logs:\n",
    "            time[t].append(idx)\n",
    "        arr = [(t, vec) for t, vec in time.items()]\n",
    "        arr.sort()\n",
    "        cnt = collections.Counter()\n",
    "        sz = 0 \n",
    "        m= len(arr) \n",
    "        l, r= 0, 0\n",
    "        ans = dict()\n",
    "        qq = copy.deepcopy(queries)\n",
    "        qq.sort()\n",
    "        for i in range(len(qq)):\n",
    "            while r < m and arr[r][0] <= qq[i]:\n",
    "                for idx in arr[r][1]:\n",
    "                    cnt[idx]+=1\n",
    "                    if cnt[idx] == 1:\n",
    "                        sz += 1\n",
    "                r += 1\n",
    "            #print(l,r, cnt,sz)\n",
    "            while l < r and arr[l][0] + x < qq[i]:\n",
    "                for idx in arr[l][1]:\n",
    "                    cnt[idx]-=1\n",
    "                    if cnt[idx] == 0:\n",
    "                        sz -= 1\n",
    "                l+=1 \n",
    "            #print(l, r,cnt,sz)\n",
    "            #print('-' * 10)\n",
    "            ans[qq[i]] = n-sz\n",
    "        \n",
    "        return [ans[q] for q in queries] \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, n: int, logs: List[List[int]], x: int, queries: List[int]) -> List[int]:\n",
    "        time = defaultdict(list)\n",
    "        for idx, t in logs:\n",
    "            time[t].append(idx)\n",
    "        arr = [(t, vec) for t, vec in time.items()]\n",
    "        arr.sort()\n",
    "        cnt = collections.Counter()\n",
    "        sz = 0 \n",
    "        m= len(arr) \n",
    "        l, r= 0, 0\n",
    "        ans = dict()\n",
    "        qq = copy.deepcopy(queries)\n",
    "        qq.sort()\n",
    "        for i in range(len(qq)):\n",
    "            while r < m and arr[r][0] <= qq[i]:\n",
    "                for idx in arr[r][1]:\n",
    "                    cnt[idx]+=1\n",
    "                    if cnt[idx] == 1:\n",
    "                        sz += 1\n",
    "                r += 1\n",
    "            #print(l,r, cnt,sz)\n",
    "            while l < r and arr[l][0] + x < qq[i]:\n",
    "                for idx in arr[l][1]:\n",
    "                    cnt[idx]-=1\n",
    "                    if cnt[idx] == 0:\n",
    "                        sz -= 1\n",
    "                l+=1 \n",
    "            #print(l, r,cnt,sz)\n",
    "            #print('-' * 10)\n",
    "            ans[qq[i]] = n-sz\n",
    "        \n",
    "        return [ans[q] for q in queries] \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
